//#pragma once
//#include<iostream>
//void Print(int* arr, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		std::cout << arr[i] << " ";
//	}
//	std::cout << std::endl;
//}
//void Swap(int& x, int& y)
//{
//	int tmp = x;
//	x = y;
//	y = tmp;
//}
//int getmidindex(int* arr,int begin,int end)
//{
//	int i = begin;
//	int back_value = arr[end];
//	for (int j=begin;j<end;j++)
//	{
//		if (arr[j]<back_value)
//		{
//			Swap(arr[j],arr[i]);
//			i++;
//		}
//	}
//	Swap(arr[i],arr[end]);
//	return i;
//}
//void QuickSort(int* arr,int begin,int end)
//{
//	if (begin>=end)
//	{
//		return;
//	}
//	int mid = getmidindex(arr,begin,end);
//	QuickSort(arr,begin,mid-1);
//	QuickSort(arr, mid+1, end);
//}
//int main()
//{
//	int arr[] = { 5,9,1,6,2,3,4,8,7,10,15,11,16,12,14,13 };
//	int size = sizeof(arr) / sizeof(int);
//	QuickSort(arr, 0,size-1);
//	Print(arr, size);
//	return 0;
//}
